A Projection-Based Reformulation and Decomposition Algorithm for Global Optimization of Mixed Integer Bilevel Linear Programs

摘要

We propose an extended variant of the reformulation and decompositionalgorithm for solving a special class of mixed-integer bilevel linear programs(MIBLPs) where continuous and integer variables are involved in both upper- andlower-level problems. In particular, we consider MIBLPs with upper-levelconstraints that involve lower-level variables. We assume that the inducibleregion is nonempty and all variables are bounded. By using the reformulationand decomposition scheme, an MIBLP is first converted into its equivalentsingle-level formulation, then computed by a column-and-constraint generationbased decomposition algorithm. The solution procedure is enhanced by aprojection strategy that does not require the relatively complete responseproperty. To ensure its performance, we prove that our new method converges tothe global optimal solution in a finite number of iterations. A large-scalecomputational study on random instances and instances of hierarchical supplychain planning are presented to demonstrate the effectiveness of the algorithm.